/**
 * Software License, Version 1.0
 * 
 * Copyright 2003 The Trustees of Indiana University.  All rights reserved.
 * 
 *
 *Redistribution and use in source and binary forms, with or without 
 *modification, are permitted provided that the following conditions are met:
 *
 *1) All redistributions of source code must retain the above copyright notice,
 * the list of authors in the original source code, this list of conditions and
 * the disclaimer listed in this license;
 *2) All redistributions in binary form must reproduce the above copyright 
 * notice, this list of conditions and the disclaimer listed in this license in
 * the documentation and/or other materials provided with the distribution;
 *3) Any documentation included with all redistributions must include the 
 * following acknowledgement:
 *
 *"This product includes software developed by the Community Grids Lab. For 
 * further information contact the Community Grids Lab at 
 * http://communitygrids.iu.edu/."
 *
 * Alternatively, this acknowledgement may appear in the software itself, and 
 * wherever such third-party acknowledgments normally appear.
 * 
 *4) The name Indiana University or Community Grids Lab or NaradaBrokering, 
 * shall not be used to endorse or promote products derived from this software 
 * without prior written permission from Indiana University.  For written 
 * permission, please contact the Advanced Research and Technology Institute 
 * ("ARTI") at 351 West 10th Street, Indianapolis, Indiana 46202.
 *5) Products derived from this software may not be called NaradaBrokering, 
 * nor may Indiana University or Community Grids Lab or NaradaBrokering appear
 * in their name, without prior written permission of ARTI.
 * 
 *
 * Indiana University provides no reassurances that the source code provided 
 * does not infringe the patent or any other intellectual property rights of 
 * any other entity.  Indiana University disclaims any liability to any 
 * recipient for claims brought by any other entity based on infringement of 
 * intellectual property rights or otherwise.  
 *
 *LICENSEE UNDERSTANDS THAT SOFTWARE IS PROVIDED "AS IS" FOR WHICH NO 
 *WARRANTIES AS TO CAPABILITIES OR ACCURACY ARE MADE. INDIANA UNIVERSITY GIVES
 *NO WARRANTIES AND MAKES NO REPRESENTATION THAT SOFTWARE IS FREE OF 
 *INFRINGEMENT OF THIRD PARTY PATENT, COPYRIGHT, OR OTHER PROPRIETARY RIGHTS. 
 *INDIANA UNIVERSITY MAKES NO WARRANTIES THAT SOFTWARE IS FREE FROM "BUGS", 
 *"VIRUSES", "TROJAN HORSES", "TRAP DOORS", "WORMS", OR OTHER HARMFUL CODE.  
 *LICENSEE ASSUMES THE ENTIRE RISK AS TO THE PERFORMANCE OF SOFTWARE AND/OR 
 *ASSOCIATED MATERIALS, AND TO THE PERFORMANCE AND VALIDITY OF INFORMATION 
 *GENERATED USING SOFTWARE.
 */
package cgl.narada.service.time.ntptime;


/**
 * This class implements NTP algorithms described in rfc 1305. Algorithms
 * implemented are combine, filter and select. It also describes static values
 * that can be used or set in the NTP protocol v3 implementation.
 * @author Hasan Bulut  - hbulut@indiana.edu
 */
public class NTP {
  //~ Static fields/initializers -----------------------------------------------

  /**
  * Version Number
  */
  public static final int VERSION = 3;

  /**
  * NTP Port
  */
  public static final int PORT = 123;

  /**
  * max clocks
  */
  public static int NMAX = 4; // 40

  /**
  * max filter size
  */
  public static int FMAX = 3;

  /**
  * clock rate
  */
  public static final int HZ = 1000;

  /**
  * Max Stratum
  */
  public static final int MAXSTRATUM = 15;

  /**
  * Max Skew error per MAXAGE
  */
  public static final int MAXSKEW = 1;

  /**
  * Max Clock Age
  */
  public static final int MAXAGE = 86400;

  /**
  * Max Distance
  */
  public static final int MAXDISTANCE = 1;

  /**
  * Min Polling Interval
  */
  public static final int MINPOLL = 6;

  /**
  * Max Polling Interval
  */
  public static final int MAXPOLL = 10;

  /**
  * Max Dispersion
  */
  public static final int MAXDISP = 16;

  /**
  * Max Dispersion
  */
  public static final double MINDISP = 0.01;

  /**
  * Reachability Reg Size
  */
  public static final int WINDOW = 8;

  /**
  * Filter Size
  */
  public static final int SHIFT = 8;

  /**
  * Min Select Clocks
  */
  public static final int MINCLOCK = 1;

  /**
  * Max Select Clocks
  */
  public static final int MAXCLOCK = 10;

  /**
  * filter weight
  */
  public static final double FILTER = 0.5;

  /**
  * select weight
  */
  public static final double SELECT = 0.75;

  //~ Instance fields ----------------------------------------------------------

  NtpTimeService timeService = NtpTimeService.getInstance();
  double[]       dist   = new double[NMAX];
  double[]       dp     = new double[NMAX];
  double[]       ep     = new double[NMAX];
  double[][]     fildp  = new double[NMAX][FMAX];
  double[][]     filep  = new double[NMAX][FMAX];
  double[][]     filtp  = new double[NMAX][FMAX];
  int[]          index  = new int[3 * NMAX];
  double[]       list   = new double[NMAX];
  double[]       rp     = new double[NMAX];
  int[]          st     = new int[NMAX];
  long[]         tao    = new long[NMAX];
  double[]       tp     = new double[NMAX];
  long[]         tstamp = new long[NMAX];
  long[]         utc    = new long[NMAX];

  /* confidence interval limits  */
  double bot;
  double delta; /* roundtrip delay */
  double epsil; /* dispersion */
  double phi    = (double) MAXSKEW / (double) MAXAGE; /* max skew rate */
  double rho    = 1. / HZ; /* max reading error */
  double theta; /* clock offset */
  double top;
  int    n1; /* min/max clock ids */
  int    n2; /* min/max clock ids */
  int    source; /* clock source */

  //~ Methods ------------------------------------------------------------------

  /**
  * Gets offset
  *
  * @return double - offset value
  */
  public double getTheta() {
    return theta;
  }

  /**
  * Computes weighted ensemble average.
  * @param m int - number of candidates to be weighted
  * @return double - combined clock offset
  */
  public double combine(int m) {
    /* int temps */
    int i;
    int j;

    /* double temps */
    double x;
    double y;
    double z;
    i = 0;
    j = 0;
    z = 0.0;
    y = 0.0;
    for (i = 0; i < m; i++) {
      /* compute weighted offset */
      j = index[i];
      x = dist[j];
      //      System.out.println("combining:"+tp[j]+" dist:"+dist[j]);
      z = z + (double) tp[j] / (double) x;
      y = y + ((double) 1.0 / (double) x);
    }
    return z / y; /* normalize */
  }

  /**
  * Computes synchronization distance.
  * @param n int - peer id
  * @return double - synchronization distance
  */
  public double dist(int n) {
    return ep[n] + phi * tao[n] + (double) Math.abs(dp[n]) / 2.0;
  }

  /**
  * Computes interval intersection, that is bot and top values.
  */
  public void dts() {
    int f; /* intersection ceiling */
    int end; /* endpoint counter */
    int clk; /* falseticker counter */

    /* int temps */
    int i;
    int j;
    int k;
    int m;
    int n;

    /* double temps */
    double x;
    double y;
    m = 0;
    i = 0;
    for (n = n1; n <= n2; n++) { /* construct endpoint list */
      if (ep[n] >= MAXDISP) {
        continue;
      }
      m       = m + 1;
      list[i] = tp[n] - dist(n);
      //      System.out.println("lowpoint: list["+i+"]:"+list[i]);
      index[i] = -1; /* lowpoint */
      for (j = 0; j < i; j++) {
        if ((list[j] > list[i]) ||
            ((list[j] == list[i]) && (index[j] > index[i]))) {
          x        = list[j];
          k        = index[j];
          list[j]  = list[i];
          index[j] = index[i];
          list[i]  = x;
          index[i] = k;
        }
      }
      i       = i + 1;
      list[i] = tp[n];
      //      System.out.println("midpoint: list["+i+"]:"+list[i]);
      index[i] = 0; /* midpoint */
      for (j = 0; j < i; j++) {
        if ((list[j] > list[i]) ||
            ((list[j] == list[i]) && (index[j] > index[i]))) {
          x        = list[j];
          k        = index[j];
          list[j]  = list[i];
          index[j] = index[i];
          list[i]  = x;
          index[i] = k;
        }
      }
      i       = i + 1;
      list[i] = tp[n] + dist(n);
      //      System.out.println("highpoint: list["+i+"]:"+list[i]);
      index[i] = 1; /* highpoint */
      for (j = 0; j < i; j++) {
        if ((list[j] > list[i]) ||
            ((list[j] == list[i]) && (index[j] > index[i]))) {
          x        = list[j];
          k        = index[j];
          list[j]  = list[i];
          index[j] = index[i];
          list[i]  = x;
          index[i] = k;
        }
      }
      i = i + 1;
    }
    if (m <= 0) {
      return;
    }
    for (f = 0; f < m / 2; f++) { /* find intersection */
      clk = 0;
      end = 0; /* lowpoint */
      for (j = 0; j < i; j++) {
        end = end - index[j];
        bot = list[j]; // bottom
        if (end >= (m - f)) {
          break;
        }
        if (index[j] == 0) {
          clk = clk + 1;
        }
      }
      end = 0; /* highpoint */
      for (j = i - 1; j >= 0; j--) {
        end = end + index[j];
        top = list[j]; // top
        if (end >= (m - f)) {
          break;
        }
        if (index[j] == 0) {
          clk = clk + 1;
        }
      }
      if (clk <= f) {
        break;
      }
    }
    return;
  }

  /**
  * It filters the NtpInfo object, which contains NTP time information received
  * from a server
  * @param ntpInfo NtpInfo - NtpInfo object related to a received NTPDatagramPacket
  */
  public void filter(NtpInfo ntpInfo) {
    int n = 0;
    n = Integer.parseInt(timeService.getServerList().get(ntpInfo.serverAddress)
                                    .toString());

    /* int temps */
    int i;
    int j;
    int k;
    int m;

    /* double temps */
    double x;
    tstamp[n]   = ntpInfo.reception;
    tao[n]      = tstamp[n] - utc[n];
    if (tao[n] < 0) {
      return;
    }
    for (i = FMAX - 1; i > 0; i--) { /*  update/shift filter */
      filtp[n][i] = filtp[n][i - 1];
      fildp[n][i] = fildp[n][i - 1];
      filep[n][i] = filep[n][i - 1] + phi * tao[n];
    }
    utc[n]      = tstamp[n];
    filtp[n][0] = ntpInfo.offset; // - tp[0];
    fildp[n][0] = ntpInfo.roundTripDelay;
    filep[n][0] = ntpInfo.rootDispersion;
    st[n]       = ntpInfo.stratum;
    m           = 0;

    /* construct/sort temp list */
    for (i = 0; i < FMAX; i++) {
      if (filep[n][i] >= MAXDISP) {
        continue;
      }
      list[m]  = filep[n][i] + (double) fildp[n][i] / 2.0;
      index[m] = i;
      for (j = 0; j < m; j++) {
        if (list[j] > list[m]) {
          x        = list[j];
          k        = index[j];
          list[j]  = list[m];
          index[j] = index[m];
          list[m]  = x;
          index[m] = k;
        }
      }
      m = m + 1;
    }
    if (m <= 0) {
      ep[n] = MAXDISP;
    } else { /* compute filter dispersion */
      ep[n] = 0;
      for (i = FMAX - 1; i >= 0; i--) {
        if (i < m) {
          x = Math.abs(filtp[n][index[0]] - filtp[n][index[i]]);
        } else {
          x = MAXDISP;
        }
        ep[n] = FILTER * (ep[n] + x);
      }
      i     = index[0];
      ep[n] = ep[n] + filep[n][i];
      tp[n] = filtp[n][i];
      dp[n] = fildp[n][i];
    }
    dist[n] = dist(n);
    return;
  }

  /**
  * Initializes the vairbales used in this class.
  */
  public void initialize() {
    // get servers info before this line and set NMAX
    int i = 0;
    int j = 0;
    if (timeService == null) {
      System.out.println("null timeservice");
    }
    NMAX   = timeService.getNumberOfServers();
    dist   = new double[NMAX];
    dp     = new double[NMAX];
    ep     = new double[NMAX];
    fildp  = new double[NMAX][FMAX];
    filep  = new double[NMAX][FMAX];
    filtp  = new double[NMAX][FMAX];
    index  = new int[3 * NMAX];
    list   = new double[3 * NMAX];
    rp     = new double[NMAX];
    st     = new int[NMAX];
    tao    = new long[NMAX];
    tp     = new double[NMAX];
    tstamp = new long[NMAX];
    utc    = new long[NMAX];
    NtpTimestamp nts = new NtpTimestamp();
    for (i = 0; i < NMAX; i++) {
      for (j = 0; j < FMAX; j++) {
        filtp[i][j] = 0;
        fildp[i][j] = 0;
        filep[i][j] = MAXDISP;
      }
      tp[i]     = 0;
      dp[i]     = 0;
      ep[i]     = 0;
      rp[i]     = 0;
      utc[i]    = nts.getTimeInMilliSeconds();
      tstamp[i] = nts.getTimeInMilliSeconds();
      tao[i]    = 0;
      st[i]     = 0;
    }
    n1 = 0;
    n2 = NMAX - 1;
  }

  /**
  * Selects best subset of clocks in candidate list
  */
  public void select() {
    double xi; /* max select dispersion */
    double eps; /* min peer dispersion */

    /* int temps */
    int i;
    int j;
    int k;
    int n;

    /* double temps */
    double x;
    double y;
    double z;
    delta = 0;
    i     = 0;
    int m = 0;
    for (n = n1; n <= n2; n++) { /* make/sort candidate list */
      if ((st[n] > 0) && (st[n] < MAXSTRATUM) && (tp[n] >= bot) &&
          (tp[n] <= top)) {
        list[m]  = MAXDISP * st[n] + dist[n];
        index[m] = n;
        for (j = 0; j < m; j++) {
          if (list[j] > list[m]) {
            x        = list[j];
            k        = index[j];
            list[j]  = list[m];
            index[j] = index[m];
            list[m]  = x;
            index[m] = k;
          }
        }
        m = m + 1;
      }
    }
    if (m <= 0) {
      source = 0;
      return;
    }
    if (m > MAXCLOCK) {
      m = MAXCLOCK;
    }
    while (true) { /* cast out falsetickers */
      xi  = 0.0;
      eps = MAXDISP;
      for (j = 0; j < m; j++) {
        x = 0.0;
        for (k = m - 1; k >= 0; k--) {
          x = SELECT * (x + Math.abs(tp[index[j]] - tp[index[k]]));
        }
        if (x > xi) {
          xi = x;
          i  = j; /* max(xi) */
        }
        x = ep[index[j]] + phi * tao[index[j]];
        if (x < eps) {
          eps = x; /* min(eps) */
        }
      }
      if ((xi <= eps) || (m <= MINCLOCK)) {
        break;
      }
      if (index[i] == source) {
        source = 0;
      }
      for (j = i; j < m - 1; j++) {
        index[j] = index[j + 1];
      }
      m = m - 1;
    }
    i = index[0];

    /* declare winner */
    if (source != i) {
      if (source == 0) {
        source = i;
      } else if (st[i] < st[source]) {
        source = i;
      }
    }
    theta = combine(m);
    delta = dp[i];
    epsil = ep[i] + phi * tao[i] + xi;
    return;
  }
}
